package com.zheng.coderepo.algorithm;

import org.junit.Assert;
import org.junit.Test;

/**
 * 爬楼梯问题。有n阶楼梯,你每次只能爬1或2阶楼梯；能有多少种方法？
 * Created by zcz on 2018/5/21.
 */
public class ClimbingStairs {

    /**
     * 递归算法
     *
     * @param n
     * @return
     */
    public int fib01(int n) {
        if (n == 1 || n == 2) {
            return n;
        } else {
            return fib01(n - 1) + fib01(n - 2);
        }
    }

    /**
     * 备忘录算法
     *
     * @param n
     * @return
     */
    public int fib02(int n) {
        if (n == 1 || n == 2) {
            return n;
        } else {
            int[] arr = new int[n + 1];
            arr[1] = 1;
            arr[2] = 2;
            return dfs(n, arr);
        }
    }

    private int dfs(int n, int[] arr) {
        if (arr[n] == 0) {
            arr[n] = dfs(n - 1, arr) + dfs(n - 2, arr);
        }
        return arr[n];
    }


    /**
     * 动态规划法
     *
     * @param n
     * @return
     */
    public int fib03(int n) {
        if (n == 1 || n == 2) {
            return n;
        } else {
            int[] arr = new int[n + 1];
            arr[1] = 1;
            arr[2] = 2;
            for (int i = 3; i <= n; i++) {
                arr[i] = arr[i - 1] + arr[i - 2];
            }

            return arr[n];
        }
    }


    /**
     * 滚动数组
     *
     * @param n
     * @return
     */
    public int fib04(int n) {
        if (n == 1 || n == 2) {
            return n;
        } else {
            int a = 1;
            int b = 2;
            int r = 0;
            for (int i = 3; i <= n; i++) {
                r = a + b;
                a = b;
                b = r;
            }

            return r;
        }
    }

    @Test
    public void testFib01() {
        Assert.assertTrue(fib01(3) == 3);
        Assert.assertTrue(fib01(4) == 5);
        Assert.assertTrue(fib01(5) == 8);
        Assert.assertTrue(fib01(6) == 13);
    }

    @Test
    public void testFib02() {
        Assert.assertTrue(fib02(3) == 3);
        Assert.assertTrue(fib02(4) == 5);
        Assert.assertTrue(fib02(5) == 8);
        Assert.assertTrue(fib02(6) == 13);
    }

    @Test
    public void testFib03() {
        Assert.assertTrue(fib03(3) == 3);
        Assert.assertTrue(fib03(4) == 5);
        Assert.assertTrue(fib03(5) == 8);
        Assert.assertTrue(fib03(6) == 13);
    }

    @Test
    public void testFib04() {
        Assert.assertTrue(fib04(3) == 3);
        Assert.assertTrue(fib04(4) == 5);
        Assert.assertTrue(fib04(5) == 8);
        Assert.assertTrue(fib04(6) == 13);
        long start = System.currentTimeMillis();
        StringBuilder stringBuilder = new StringBuilder();
        for (int i =0; i< 1000000;i++) {
            stringBuilder.append("H");
        }
        System.out.println(System.currentTimeMillis() - start);

        start = System.currentTimeMillis();
        String str = "";
        for (int i =0; i< 1000000;i++) {
            str = str + "H";
        }
        System.out.println(System.currentTimeMillis() - start);

    }
//    public String  change(String str) {
//
//        return a;
//    }
}
